<head>
    <meta charset="UTF-8">
<title>算法训练 小生物的逃逸</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <!--[if gte mso 9]><xml><w:WordDocument><w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel><w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery><w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery><w:DocumentKind>DocumentNotSpecified</w:DocumentKind><w:DrawingGridVerticalSpacing>7.8</w:DrawingGridVerticalSpacing><w:View>Normal</w:View><w:Compatibility><w:DontGrowAutofit /></w:Compatibility><w:Zoom>0</w:Zoom></w:WordDocument></xml><![endif]-->
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">【问题描述】</span></p>
<p style="text-indent:21.0000pt; margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">空间中有<font face="Times New Roman">n</font><font face="宋体">个球，这些球不相交也不相切。有</font><font face="Times New Roman">m</font><font face="宋体">个可以视为质点的小生物，可能在某些球内，也可能在所有球之外，但不会在球面上。问这些生物从原来的地方逃逸到所有球外面的空间，至少要经过多少层球面。</font></span></p>
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">【输入格式】</span></p>
<p style="text-indent:21.0000pt; margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">第一行两个数<font face="Times New Roman">n</font><font face="宋体">、</font><font face="Times New Roman">m</font><font face="宋体">：表示球的数量和小生物的数量；</font></span></p>
<p style="text-indent:21.0000pt; margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">接下来<font face="Times New Roman">n</font><font face="宋体">行每行四个整数</font><font face="Times New Roman">Xi</font><font face="宋体">、</font><font face="Times New Roman">Yi</font><font face="宋体">、</font><font face="Times New Roman">Zi</font><font face="宋体">和</font><font face="Times New Roman">Ri</font><font face="宋体">：表示一个球的三维坐标和半径；</font></span></p>
<p style="text-indent:21.0000pt; margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">接下来<font face="Times New Roman">m</font><font face="宋体">行每行三个整数</font><font face="Times New Roman">Xi</font><font face="宋体">、</font><font face="Times New Roman">Yi</font><font face="宋体">、</font><font face="Times New Roman">Zi</font><font face="宋体">：表示一个生物的坐标。</font></span></p>
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">【输出格式】</span></p>
<p style="text-indent:21.0000pt; margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">一行<font face="Times New Roman">m</font><font face="宋体">个数：表示每个小生物逃逸时至少经过的球面数。</font></span></p>
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">【样例输入】</span></p>
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">2&nbsp;2</span></p>
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">0&nbsp;0&nbsp;0&nbsp;2</span></p>
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">0&nbsp;0&nbsp;0&nbsp;4</span></p>
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">0&nbsp;0&nbsp;1</span></p>
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">0&nbsp;0&nbsp;3</span></p>
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">【样例输出】</span></p>
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">2&nbsp;1</span></p>
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">【数据规模和约定】</span></p>
<p style="text-indent:21.0000pt; margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">1&lt;=n<font face="宋体">、</font><font face="Times New Roman">m&lt;=100</font><font face="宋体">，</font><font face="Times New Roman">|Xi|</font><font face="宋体">、</font><font face="Times New Roman">|Yi|</font><font face="宋体">、</font><font face="Times New Roman">|Zi|&lt;=10000</font><font face="宋体">，</font><font face="Times New Roman">1&lt;=Ri&lt;=10000</font><font face="宋体">；</font></span></p>
<p style="text-indent:21.0000pt; margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">数据保证所有球严格不接触，小生物都不在球面上。</span></p>
<p style="margin-bottom:0pt; margin-top:0pt; " class="p0"><span style="mso-spacerun:'yes'; font-size:10.5000pt; font-family:'宋体'; ">&nbsp;</span></p>
<!--[if gte mso 9]><xml><w:LatentStyles DefLockedState="false"  DefUnhideWhenUsed="true"  DefSemiHidden="true"  DefQFormat="false"  DefPriority="99"  LatentStyleCount="156" ><w:LsdException Locked="false"  Priority="99"  Name="Normal" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="heading 1" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="heading 2" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="heading 3" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="heading 4" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="heading 5" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="heading 6" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="heading 7" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="heading 8" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="heading 9" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="index 1" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="index 2" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="index 3" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="index 4" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="index 5" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="index 6" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="index 7" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="index 8" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="index 9" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="toc 1" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="toc 2" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="toc 3" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="toc 4" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="toc 5" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="toc 6" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="toc 7" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="toc 8" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="toc 9" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Normal Indent" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="footnote text" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="annotation text" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="header" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="footer" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="index heading" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="caption" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="table of figures" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="envelope address" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="envelope return" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="footnote reference" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="annotation reference" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="line number" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="page number" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="endnote reference" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="endnote text" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="table of authorities" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="macro" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="toa heading" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Bullet" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Number" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List 2" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List 3" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List 4" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List 5" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Bullet 2" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Bullet 3" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Bullet 4" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Bullet 5" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Number 2" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Number 3" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Number 4" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Number 5" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Title" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Closing" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Signature" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Default Paragraph Font" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Body Text" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Body Text Indent" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Continue" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Continue 2" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Continue 3" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Continue 4" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="List Continue 5" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Message Header" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Subtitle" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Salutation" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Date" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Body Text First Indent" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Body Text First Indent 2" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Note Heading" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Body Text 2" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Body Text 3" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Body Text Indent 2" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Body Text Indent 3" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Block Text" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Hyperlink" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="FollowedHyperlink" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Strong" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Emphasis" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Document Map" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Plain Text" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="E-mail Signature" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Normal (Web)" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="HTML Acronym" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="HTML Address" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="HTML Cite" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="HTML Code" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="HTML Definition" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="HTML Keyboard" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="HTML Preformatted" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="HTML Sample" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="HTML Typewriter" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="HTML Variable" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Normal Table" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="annotation subject" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="No List" ></w:LsdException><w:LsdException Locked="false"  Priority="99"  Name="Balloon Text" ></w:LsdException></w:LatentStyles></xml><![endif]-->